#include <bits/stdc++.h>

using namespace std;

// 跳跃游戏II
// 给定一个长度为n的0索引整数数组nums，初始位置为nums[0]
// 每个元素nums[i]表示从索引i向前跳转的最大长度
// 换句话说，如果你在nums[i]处，你可以跳转到任意nums[i+j]处
// 0 <= j <= nums[i] 
// i + j < n
// 返回到达nums[n - 1]的最小跳跃次数
// 生成的测试用例可以到达nums[n-1]
// 测试链接 : https://leetcode.cn/problems/jump-game-ii/

class Solution 
{
public:
    int jump(vector<int>& nums) 
    {
        // 当前步以内，最右到哪
        int cur = 0;
        // 如果再一步，(当前步+1)以内，最右到哪
        int next = 0;
        // 一共需要跳几步
        int ans = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(cur < i)
            {
                ++ans;
                cur = next;
            }
            next = max(next, i + nums[i]);
        }
        return ans;
    }
};